Deep learning models are vulnerable to privacy attacks due to their tendency to memorize individual training examples. Theoretically-sound defenses such as differential privacy can defend against this threat, but model performance often suffers. Empirical defenses may thwart existing attacks while maintaining model performance but do not offer any robust theoretical guarantees. In this paper, we explore a new strategy based on the concept of plausible deniability. We introduce a training algorithm called Plausibly Deniable Stochastic Gradient Descent (PD-SGD). The core of this approach is a rejection sampling technique, which probabilistically prevents updating model parameters whenever a mini-batch cannot be plausibly denied. We provide theoretical results showing that PD-SGD effectively mitigates privacy leakage from individual data points. Experiments demonstrate the scalability of PD-SGD and the favorable privacy-utility trade-off it offers compared to existing defense methods.

As major progress in LLM-based long-form text generation enables paradigms such as retrieval-augmented generation (RAG) and inference-time scaling, safely incorporating private information into the generation remains a critical open question.

We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected graph, we treat the weights of edges as sensitive information, and two graphs are neighbors if their edge weights differ in one edge by at most one. We obtain efficient algorithms with significantly improved bounds on a broad class of graphs which we refer to as recursively separable. In particular, for any n-vertex Kh-minor-free graph, our algorithm achieve an additive error of eO(h(nW)1/3), where W represents the maximum edge weight; For grid graphs, the same algorithmic scheme achieve additive error of eO(n1/4 W). Our approach can be seen as a generalization of the celebrated binary tree mechanism for range queries, as releasing range queries is equivalent to computing all-pair distances on a path graph. In essence, our approach is based on generalizing the binary tree mechanism to graphs that are recursively separable. JL and ZZ have been supported by National Science Foundation of China under Grant No. 62472212 and the New Cornerstone Science Foundation. Supported in part by NSF award 2228995 JU's research was funded by the NSFCNS 2433628, Google Seed Fund grant, Google Research Scholar Award, Dean Research Seed Fund, and Rutgers Decanal Grant no.

Differentially private (DP) decentralized Federated Learning (FL) allows local users to collaborate without sharing their data with a central server. However, accurately quantifying the privacy budget of private FL algorithms is challenging due to the co-existence of complex algorithmic components such as decentralized communication and local updates.

We revisit the problem of private online learning, in which a learner receives a sequence of T data points and has to respond at each time-step a hypothesis. It is required that the entire stream of output hypotheses should satisfy differential privacy. Prior work of Golowich and Livni [2021] established that every concept class H with finite Littlestone dimension d is privately online learnable in the realizable setting. In particular, they proposed an algorithm that achieves an Od(logT) mistake bound against an oblivious adversary. However, their approach yields a suboptimal Od( T) bound against an adaptive adversary. In this work, we present a new algorithm with a mistake bound of Od(logT)against an adaptive adversary, closing this gap. We further investigate the problem in the agnostic setting, which is more general than the realizable setting as it does not impose any assumptions on the data. We give an algorithm that obtains a sublinear regret of Od( T) for generic Littlestone classes, demonstrating that they are also privately online learnable in the agnostic setting.

Given an undirected, weighted n-vertex graph G = (V,E,w), a Gomory-Hu tree T is a weighted tree on V that preserves the Min-s-t-Cut between any pair of vertices s,t V. Finding cuts in graphs is a key primitive in problems such as bipartite matching, spectral and correlation clustering, and community detection. We design a differentially private (DP) algorithm that computes an approximate Gomory-Hu tree. Our algorithm is ε-DP, runs in polynomial time, and can be used to compute s-tcuts that are O(n/ε)-additive approximations of the Min-s-t-Cuts in Gfor all distinct s,t V with high probability. Our error bound is essentially optimal, since [29] showed that privately outputting a single Min-s-t-Cut requires Ω(n) additive error even with (ε,δ)-DP and allowing for multiplicative error. Prior to our work, the best additive error bounds for approximate all-pairs Min-s-t-Cuts were O(n3/2/ε)for ε-DP [47] and O( mn/ε)for (ε,δ)-DP [66], both achieved by DP algorithms that preserve all cuts in the graph. To achieve our result, we develop an ε-DP algorithm for the Minimum Isolating Cuts problem with near-linear error, and introduce a novel privacy composition technique combining elements of both parallel and basic composition to handle'bounded overlap' computational branches in recursive algorithms, which maybe of independent interest.

We study the problem of sampling from a distribution under local differential privacy (LDP). Given a private distribution P P, the goal is to generate a single sample from a distribution that remains close to P in f-divergence while satisfying the constraints of LDP.

We propose a framework to convert (ε,δ)-approximate Differential Privacy (DP) mechanisms into (ε,0)-pure DP mechanisms under certain conditions, a process we call "purification." This algorithmic technique leverages randomized postprocessing with calibrated noise to eliminate the δ parameter while achieving nearoptimal privacy-utility tradeoff for pure DP. It enables a new design strategy for pure DP algorithms: first run an approximate DP algorithm with certain conditions, and then purify. This approach allows one to leverage techniques such as strong composition and propose-test-release that require δ > 0 in designing pure-DP methods with δ = 0. We apply this framework in various settings, including Differentially Private Empirical Risk Minimization (DP-ERM), stability-based release, and query release tasks. To the best of our knowledge, this is the first work with a statistically and computationally efficient reduction from approximate DP to pure DP. Finally, we illustrate the use of this reduction for proving lower bounds under approximate DP constraints with explicit dependence in δ, avoiding the sophisticated fingerprinting code construction.

We propose a practical sequential test for auditing differential privacy guarantees of black-box mechanisms. The test processes streams of mechanisms' outputs providing anytime-valid inference while controlling Type I error, overcoming the fixed sample size limitation of previous batch auditing methods. Experiments show this test detects violations with sample sizes that are orders of magnitude smaller than existing methods, reducing this number from 50K to a few hundred examples, across diverse realistic mechanisms. Notably, it identifies DP-SGD privacy violations in under one training run, unlike prior methods needing full model training.

In the approximate quantiles problem, the goal is to output mquantile estimates, the ranks of which are as close as possible to m given quantiles 0 q1 qm 1. We present a mechanism for approximate quantiles that satisfies ε-differential privacy for a dataset of n real numbers where the ratio between the distance between the closest pair of points and the size of the domain is bounded by ψ.